//https://leetcode.cn/problems/next-greater-element-i/
//496. 下一个更大元素 I





/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* nextGreaterElement(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    // 找到nums2数组中的最大值，用于确定哈希映射数组的大小
    int max_val = 0;
    for (int i = 0; i < nums2Size; i++) {
        if (nums2[i] > max_val) {
            max_val = nums2[i];
        }
    }
    
    // 创建哈希映射数组，大小为max_val+1，初始值设为-1
    int* nextMap = (int*)malloc((max_val + 1) * sizeof(int));
    for (int i = 0; i <= max_val; i++) {
        nextMap[i] = -1;
    }
    
    // 创建栈用于单调栈算法
    int* stack = (int*)malloc(nums2Size * sizeof(int));
    int top = -1;  // 栈顶指针
    
    // 使用单调栈算法计算nums2中每个元素的下一个更大元素
    for (int i = 0; i < nums2Size; i++) {
        // 当栈不为空且当前元素大于栈顶元素时
        while (top != -1 && nums2[stack[top]] < nums2[i]) {
            int idx = stack[top--];  // 弹出栈顶元素
            nextMap[nums2[idx]] = nums2[i];  // 记录栈顶元素的下一个更大元素
        }
        stack[++top] = i;  // 将当前元素索引入栈
    }
    free(stack);  // 释放栈内存
    
    // 创建结果数组
    int* ans = (int*)malloc(nums1Size * sizeof(int));
    // 遍历nums1，通过哈希映射获取每个元素的下一个更大元素
    for (int i = 0; i < nums1Size; i++) {
        ans[i] = nextMap[nums1[i]];
    }
    free(nextMap);  // 释放哈希映射内存
    
    *returnSize = nums1Size;  // 设置返回数组的大小
    return ans;  // 返回结果数组
}